UVa/574 - Sum it up/574.cpp

   1 /*
   2   Problem: 574 - Sum it up (UVa Online Judge)
   3   Accepted
   4
   5   Author: Andrés Mejía-Posada
   6  */
   7 #include <iostream>
   8 #include <cassert>
   9 #include <vector>
  10 #include <algorithm>
  11
  12 using namespace std;
  13
  14 typedef vector< vector<int> > matrix;
  15
  16 //for sorting the answer
  17 bool compare(const vector<int> &a, const vector<int> &b) {
  18   int n = a.size(), m = b.size();
  19   for (int i=0; i<n && i<m; ++i){
  20     if (a[i] > b[i]) return true;
  21     if (b[i] > a[i]) return false;
  22   }
  23   return n < m;
  24 }
  25
  26 void show(const vector<int> &v){
  27   printf("%d", v[0]);
  28   for (int i=1, n=v.size(); i<n; ++i){
  29     printf("+%d", v[i]);
  30   }
  31   printf("\n");
  32 }
  33
  34 int main(){
  35   int t, n;
  36   while (scanf("%d %d", &t, &n) == 2 && n){
  37     int m[n];
  38     matrix dp[n][t+1];
  39     for (int i=0; i<n; ++i){
  40       scanf("%d", &m[i]);
  41     }
  42
  43     dp[0][0].push_back(vector<int>());
  44     if (m[0] <= t){
  45       dp[0][m[0]].push_back(vector<int>(1, m[0]));
  46     }
  47     for (int i=1; i<n; ++i){
  48       for (int j=0; j<=t; ++j){
  49         dp[i][j] = dp[i-1][j];
  50         if (j - m[i] >= 0){
  51           for (int k=0; k<dp[i-1][j-m[i]].size(); ++k){
  52             dp[i][j].push_back(dp[i-1][j-m[i]][k]);
  53             dp[i][j].back().push_back(m[i]);
  54           }
  55         }
  56       }
  57     }
  58
  59     /*for (int i=0; i<n; ++i){
  60       for (int j=0; j<=t; ++j){
  61         printf("(%d, %d) %d elementos: \n", i, j, dp[i][j].size());
  62         for (int k=0; k<dp[i][j].size(); ++k){
  63           for (int m=0; m<dp[i][j][k].size(); ++m){
  64             printf("%d ", dp[i][j][k][m]);
  65           }
  66           printf("\n");
  67         }
  68         printf("\n");
  69       }
  70       }*/
  71     matrix &answer = dp[n-1][t];
  72     sort(answer.begin(), answer.end(), compare);
  73
  74     //printf("La respuesta tiene %d elementos\n", dp[n-1][t].size());
  75     printf("Sums of %d:\n", t);
  76     if (answer.size() == 0){
  77       printf("NONE\n");
  78     }else{
  79       show(answer[0]);
  80       for (int i=1; i<answer.size(); ++i){
  81         if (answer[i] != answer[i-1]) show(answer[i]);
  82       }
  83     }
  84   }
  85   return 0;
  86 }